Data communication switches receive packets on a plurality of inputs and transmit them on a plurality of outputs. Sometimes, packets come in on two or more inputs destined for the same output. To minimize collisions between such packets, queueing is used. Queues temporarily store some packets while others are consuming the bandwidth necessary for delivery of the queued packets to an output.
The release of packets from queues competing for output bandwidth is typically coordinated by a scheduler. Many schedulers honor a strict rule of priority scheduling, that is, queues are assigned different priority levels and those associated with relatively high priority levels are allowed to release packets before those associated with relatively low priority levels. Strict priority scheduling allows flows which have been designated as relatively time-critical to take precedence over those which have been designated as relatively less time critical.
Despite its general efficacy, strict priority scheduling is not problem-free. One undesirable effect is priority blocking. Priority blocking occurs when delivery of packets from relatively low priority queues suffer a sustained delay due to servicing of higher priority queues. Priority blocking can eventually cause packets in the blocked queues to be overwritten while awaiting release, a condition known as dropping. Dropping undesirably disrupts the flows to which the dropped packets relate.
While priority scheduling is by design supposed to provide faster service to some queues than others, departure from a strict rule of prioritization may be warranted in certain cases. For instance, priority blocking may be caused by “stuffing” of a single queue at the priority level receiving service with non-critical or even redundant (e.g., in the case of an unresolved spanning tree loop) traffic. Strict adherence to priority scheduling would allow this “stuffing” to in effect hold all of the output bandwidth hostage at the expense of the relatively low priority queues.
Accordingly, there is a need for a qualified priority scheduling method for reducing priority blocking through the imposition of reasonable limitations on a general policy of prioritization. There is also a need for efficient scheduling hardware to effectuate the qualified priority scheduling.